package SelectSort;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] a = {89,12,34,25,78,43,78,23};
        heapSort(a);
        System.out.println(Arrays.toString(a));
        Arrays.sort(a);
        System.out.println(Arrays.toString(a));
    }
    //时间复杂度O(nlogn)
    //空间复杂度O(1)
    //稳定性:不稳定
    private static void heapSort(int[] a) {
        GreateBigHeap(a);
        int end = a.length - 1;
        while (end > 0){
            swap(a,0,end);
            shitfDown(a,0,end);
            end--;

        }

    }

    private static void GreateBigHeap(int[] a) {
        for (int parent = (a.length-1-1)/2; parent >= 0 ; parent--) {
            shitfDown(a,parent,a.length);

        }
    }

    private static void shitfDown(int[] a, int parent, int len) {
        int child = 2 *parent +1;
        while (child < len ){
            if (child+1 < len && a[child+1] > a[child] ){
                child++;
            }
            if(a[child] > a[parent]){
                swap(a,child,parent);
                parent = child;
                child = 2*parent +1;
            }else {
                break;
            }
        }
    }


    private static void swap(int[] a, int i, int end) {
        int tmp = a[i];
        a[i] = a[end];
        a[end] = tmp;
    }

}